package singlelistdemo;

public class MySingleList {
    static class Node {
        public int val;
        public Node next;
        public Node(int val) {
            this.val = val;
        }
        public Node head;
        public void createList() {
            Node node1 = new Node(11);
            Node node2 = new Node(22);
            Node node3 = new Node(33);
            Node node4 = new Node(44);
            head = node1;
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = null;
        }

        //头插
        public void addFirst(int val) {
            Node newNode = new Node(val);
            newNode.next = head;
            head = newNode;
        }

        //尾插
        public void addLast(int val) {
            Node newNode = new Node(val);
            Node cur = head;
            while(cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode;
            newNode.next = null;
        }

        //获取链表的长度
        public int size() {
            int count = 0;
            Node cur = head;
            while(cur != null) {
                count++;
                cur = cur.next;
            }
            return count;
        }

        //打印链表
        public void print() {
            Node cur = head;
            while(cur != null) {
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
        }

        //查找是否包含元素key
        public boolean contains(int key) {
            Node cur = head;
            while(cur != null) {
                if(cur.val == key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }

        //在index下标位置插入节点值为val的新节点
        public void addIndex(int index,int val) {
            if(index < 0 || index > size()-1) {
                throw new PosOutOfException("下标不合法");
            }
            if(index == 0) {
                addFirst(val);
            }else if(index == size()-1) {
                addLast(val);
            }else {
                Node cur = head;
                for (int i = 0; i < index-1; i++) {
                    cur = cur.next;
                }
                Node newNode = new Node(val);
                newNode.next = cur.next;
                cur.next = newNode;
            }
        }
    }
}
